/*
151. 反转字符串中的单词
. 中等

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
*/

#include <iostream>
#include <string>

using namespace std;

class Solution {
public:
    string reverseWords(string s) {
        //1.去多余的空格
        auto slow = s.begin();
        auto fast = s.begin();
        while(fast!=s.end())
        {
            if(*fast!=' ')
            {
                break;
            }
            fast++;
        }

        while(fast!=s.end())
        {
            if (fast>s.begin()&&*fast==*(fast-1)&&*fast==' ')
                {
                    fast++;
                    continue;
                }
            *slow = *fast;
            slow++;
            fast++;
        }
        int size;
        slow--;
        if(*(slow)==' ')
        {
            size = slow - 1 - s.begin() + 1;
        }
        else
        {
            size = slow - s.begin() + 1;
        }
        s.resize(size); // 重新设置字符串大小
        //2.翻转整个字符串
        auto left = s.begin();
        auto right = s.end() - 1;
        while(left<right)
        {
            char temp=*right;
            *right = *left;
            *left = temp;
            left++;
            right--;
        }

        //3.再次翻转每个单词
        auto left_const = s.begin();
        auto right_const = s.begin();
        while(right_const!=s.end())
        {
            if(*(right_const+1)==' '||right_const+1==s.end())
            {
                left = left_const;
                right = right_const;
                while(left<right)
                {
                    char temp=*right;
                    *right = *left;
                    *left = temp;
                    left++;
                    right--;
                }
                left_const = right_const + 2;
            }
            right_const++;
            
        }
        return s;
    }
};

int main()
{
    string s = "  hello world  ";
    Solution sl;
    s=sl.reverseWords(s);
    cout << s;
    return 0;
}
